#!/usr/bin/python

import random
import sys
import string 
import os
import time
print sys.getrecursionlimit()
sys.setrecursionlimit(5000)	
print sys.getrecursionlimit()
#sys.exit()
#filas
n = 10
#columnas
m = 10

DEBUG=0
def debug(s):
	if DEBUG :
		print s


# las fichas se numeran asi en sus coordenadas
# 	2
# 1   3
# 	4
def crearFicha():
	return [ random.randint(1,4) for i in range(4) ]

def crearFichaComodin():
	return [ 0 for i in range(4) ]

def crearFichaDebug():
	return [ 8 for i in range(4) ]


def fichaEncaja(ficha,izquierda=None ,arriba=None):
	return  ( ( not izquierda or izquierda[2] == ficha[0] or izquierda[2] == 0 ) and
			( not arriba or arriba[3] == ficha[1] or arriba[3] == 0 ) )

def printTablero(tablero, index=None):
	global n, m, comodinesActual, mejorSolucionComodines
	os.system('clear')
	defaultBackground = ' '
	currentBackground = defaultBackground
	for i in range(n):
		
		for t in range(m*6):
			sys.stdout.write('-')
		sys.stdout.write('\n')

		for ii in range(3):	
			for j in range(m):
				if (i*m + j) ==  index  :
					currentBackground = chr(64)
				else:
					currentBackground = defaultBackground 

				for jj  in range(3):					
					if ii == 0 and  jj == 0 :
						sys.stdout.write(currentBackground)
					if ii == 0 and  jj == 2 :
						sys.stdout.write(currentBackground)
					if ii == 2 and  jj == 0 :
						sys.stdout.write(currentBackground)
					if ii == 2 and  jj == 2 :
						sys.stdout.write(currentBackground)
					if ii == 1 and jj == 1 :
						sys.stdout.write(currentBackground)
					if ii == 1 and jj == 0:
						sys.stdout.write('%s' %  tablero[i*m + j][0] )	
					if ii == 1 and  jj == 2:
						sys.stdout.write('%s' %  tablero[i*m + j][2] )	
					if ii == 0 and jj == 1:
						sys.stdout.write( '%s' %  tablero[i*m + j][1] )	
					if jj == 1 and ii == 2:
						sys.stdout.write( '%s' %  tablero[i*m + j][3] )	
					#else:
				sys.stdout.write(' | ')
			sys.stdout.write("\n")
	for t in range(m*6):
		sys.stdout.write('-')
	sys.stdout.write('-  current [%s]  mejor [%s]\n' % (comodinesActual,mejorSolucionComodines) )
	debug("                                              ")
	time.sleep(0.1)

def esComodin(ficha):
	return ficha[0] == 0

def dameFichaQueEncaje(izquierda=None,arriba=None):
	global fichas
	ficha = None
	otras = 0
	for f in range(len(fichas)):
		if f < len(fichas) and fichaEncaja(fichas[f],izquierda,arriba):
			otras += 1
			if otras == 1:
				ficha=fichas[f]
				fichas.remove(ficha)
	if otras:
		return (otras,ficha)
	return (1, crearFichaComodin())

def posicionarFicha(tablero,i,ficha):
	tablero[i] = ficha

def getArriba(tablero,i):
	if i >= m:
		return tablero[i-m]
	return crearFichaComodin()

def getIzquierda(tablero,i):
	if (i % m ) != 0 : 
		return tablero[i-1]
	return crearFichaComodin()




def encontrarTablero(i):
	global comodinesActual, n, m, mejorTablero,mejorSolucionComodines, comodinesUsados
	while True:
		debug("---------------------- paso  %s intento %s comodines %s " % \
		(i, intentosPorPosicion[i] if i in intentosPorPosicion else 0 ,comodinesActual))
		com  = crearFichaComodin()
		if com in fichas:
			fichas.remove(com)

		if i >= n*m:
			if comodinesActual < mejorSolucionComodines:
				mejorSolucionComodines = comodinesActual
				mejorTablero = tableroActual[0:len(tableroActual)]

			if len(comodinesUsados):
				debug("llegue al final busco mejor solucion")
				posUltimoComodin = comodinesUsados.pop_back();
				comodinesActual -= 1
				for t in range(posUltimoComodin,n*m):
					debug("devuelvo fincha ")
					intentosPorPosicion[t] = 0
					if i != posUltimoComodin:
						fichas.push_back(tableroActual[t]);
						
					d = crearFichaDebug()
					posicionarFicha(tableroActual,t,d)										
				#encontrarTablero(posUltimoComodin-1)			
				#return	
				i = posUltimoComodin-1
				continue
			else:
				debug("solucion sin comodines !!!!!")
				break 
			debug("cantidad de comodines %s" % mejorSolucionComodines)
			break
		if i < 0:
			debug( "cantidad de comodines %s end" % mejorSolucionComodines)
			printTablero(mejorTablero)
			break

		#############################

		if i  not in intentosPorPosicion or intentosPorPosicion[i] == 0 :
			#avanzo en una rama
			izquierda=getIzquierda(tableroActual,i)
			arriba=getArriba(tableroActual,i)
			ficha = dameFichaQueEncaje(izquierda,arriba)

			intentosPorPosicion[i] = ficha[0]
		else:
			#tuve que volver hacia atras
			intentosPorPosicion[i] -= 1

			if intentosPorPosicion[i] < 1:
				if i == 0:
					debug( "cantidad de comodines %s end" % mejorSolucionComodines)
					printTablero(mejorTablero)
					break
				else:			
					#devuelvo la ficha anterior al las disponibles 
					intentosPorPosicion[i] = 0
					if esComodin(tableroActual[i-1]):
						comodinesActual -= 1
						comodinesUsados.remove(i-1)
					else:
						fichas.append(tableroActual[i-1] )						
					d = crearFichaDebug()
					posicionarFicha(tableroActual,i,d)
					debug( string.join( [ '%s=>%s  '  % (k,v) for k, v in  intentosPorPosicion.items() ], ''))
					debug("------------------------------       retrocedo por intentos")
					#encontrarTablero(i-1)
					i = i-1
					continue
					#return 
			else:
				izquierda=getIzquierda(tableroActual,i)
				arriba=getArriba(tableroActual,i)
				ficha = dameFichaQueEncaje(izquierda,arriba)
		#############################
		if esComodin(ficha[1]) :
			debug("comodines actual %s comodines mejor %s " % (comodinesActual, mejorSolucionComodines))
			if comodinesActual + 1 >= mejorSolucionComodines:
				#devuelvo la ficha anterior al las disponibles 
				if esComodin(tableroActual[i-1]):
					comodinesActual -= 1
					comodinesUsados.remove(i-1)
				else:
					fichas.append(tableroActual[i-1] )
				intentosPorPosicion[i] = 0
				d = crearFichaDebug()
				posicionarFicha(tableroActual,i,d)
				printTablero(tableroActual,i)
				debug(string.join( [ '%s=>%s  '  % (k,v) for k, v in  intentosPorPosicion.items() ], ''))
				debug("-------------------------------  retrocedo  por comodin")
				#intentosPorPosicion[i] = ficha[0]
				#encontrarTablero(i-1)
				i = i-1
				continue
				#return 
			else:
				posicionarFicha(tableroActual,i,ficha[1])
				comodinesActual += 1 
				comodinesUsados.append(i)
				printTablero(tableroActual,i)
				debug(string.join( [ '%s=>%s  '  % (k,v) for k, v in  intentosPorPosicion.items() ], '')	)
				debug("=================================== pongo comodin")
				#encontrarTablero(i+1)			
				#return 
				i = i+1
				continue
		else:		
			posicionarFicha(tableroActual,i,ficha[1])
			#intentosPorPosicion[i] = ficha[0]
			printTablero(tableroActual,i)
			debug( string.join( [ '%s=>%s  '  % (k,v) for k, v in  intentosPorPosicion.items() ], '')	)
			debug("###################################### pongo ficha")
			#encontrarTablero(i+1)
			#return 
			i = i+1
			continue



fichas = [ crearFicha() for i in range(n*m) ]

mejorSolucionComodines = n*m
mejorTablero = [ crearFichaComodin() for i in range(n*m)] 

comodinesActual = 0
tableroActual = [ crearFichaDebug() for i in range(n*m) ]

comodinesUsados = []

printTablero(tableroActual)

empezarEn=random.randint(0,n*m-1)
primeraFicha = fichas[empezarEn]
fichas.remove(fichas[empezarEn])
posicionarFicha(tableroActual,0,primeraFicha)
intentosPorPosicion=dict({0:n*m-1})
encontrarTablero(1)

